import java.util.*;

/**
 * @author huangxin
 * @date 2020/8/19-16:51
 */
public class LeetCode {
    public int lastStoneWeight(int[] stones) {


        if (stones.length == 1) {
            return stones[0];
        }
        if (stones.length == 2) {
            return Math.abs(stones[0] - stones[1]);
        }

        while (stones[stones.length - 3] != 0) {
            Arrays.sort(stones);
            if (stones[stones.length - 1] == stones[stones.length - 2]) {
                stones[stones.length - 2] = 0;
            } else if (stones[stones.length - 1] > stones[stones.length - 2]) {
                stones[stones.length - 2] = stones[stones.length - 1] - stones[stones.length - 2];
            }
            stones[stones.length - 1] = 0;
        }

        return stones[stones.length - 2] - stones[stones.length - 1];
    }


    public int binaryGap(int n) {
        StringBuilder str = new StringBuilder();
        int max = 0;
        int spac = 0;
        boolean flag = true;
        while (n != 0) {
            int num = n % 2;


            spac++;
            if (num == 1) {
                if (flag) {
                    flag = false;
                } else {
                    max = Math.max(spac, max);
                }
                spac = 0;
            }

            str.insert(0, n % 2);
            n /= 2;
        }
        return max;

    }

    public int removeElement(int[] nums, int val) {

        int count = nums.length;
        for (int i = 0; i < nums.length; i++) {
            if (val == nums[i]) {
                nums[i] = Integer.MAX_VALUE;
                count--;
            }

        }

        Arrays.sort(nums);

        return count;
    }


    public String removeDuplicates(String S) {
        if (S.length() < 2) {
            return S;
        }

        char[] chars = new char[S.length()];

        int index = 0;

        for (int i = 0; i < S.length(); i++) {
            if (index > 0 && chars[index - 1] == S.charAt(i)) {
                index--;
            } else {
                chars[index++] = S.charAt(i);
            }

        }


        return new String(chars, 0, index);

    }


    public List<String> subdomainVisits(String... cpdomains) {
        HashMap<String, Integer> map = new HashMap<>();

        for (String cpdomain : cpdomains) {
            String[] split = cpdomain.split(" ");
            int num = Integer.parseInt(split[0]);

            String[] domains = split[1].split("\\.");


            for (int i = domains.length - 2; i >= 0; i--) {
                domains[i] += "." + domains[i + 1];
            }

            for (int i = domains.length - 1; i >= 0; i--) {
                map.put(domains[i], map.getOrDefault(domains[i], 0) + num);
            }

        }


        ArrayList<String> list = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            String str = entry.getValue() +
                    " " +
                    entry.getKey();
            list.add(str);
        }
        return list;
    }


    public int countPrimeSetBits(int L, int R) {

        List<Integer> list = Arrays.asList(2, 3, 5, 7, 11, 13);

        int count = 0;
        for (int i = L; i <= R; i++) {
            if (list.contains(getPrimeNumCount(i))) {
                count++;
            }
        }

        return count;
    }


    public int getPrimeNumCount(int n) {
        int count = 0;

        while (n != 0) {
            count += n % 2;
            n /= 2;
        }

        return count;
    }


    public int[] sortArrayByParityII(int[] arr) {
        int[] result = new int[arr.length];

        for (int i = 0, j = 0, k = 1; i < arr.length; i++) {
            if (arr[i] % 2 == 0) {
                result[j] = arr[i];
                j += 2;
            } else {
                result[k] = arr[i];
                k += 2;
            }
        }

        return result;
    }

    public int calPoints(String... ops) {
        int[] arr = new int[ops.length];
        int index = 0;
        for (int i = 0; i < ops.length; i++) {
            if ("D".equals(ops[i])) {
                arr[index] = arr[index - 1] * 2;
                index++;
            } else if ("+".equals(ops[i])) {
                arr[index] = arr[index - 1] + arr[index - 2];
                index++;
            } else if ("C".equals(ops[i])) {
                index--;
            } else {
                arr[index++] = Integer.parseInt(ops[i]);
            }
        }

        int sum = 0;

        for (int i = 0; i < index; i++) {
            sum += arr[i];
        }

        return sum;
    }

    public int titleToNumber(String s) {
        if (s.length() == 0) {
            return 0;
        }

        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            result = result * 26 + (s.charAt(i) - 'A' + 1);
        }

        return result;
    }

    public int minStartValue(int... nums) {
        int min = nums[0];
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            min = Math.min(sum, min);
        }

        return min < 0 ? 1 - min : 1;

    }


    public int addDigits(int num) {
        int result = 0;

        while (num != 0) {
            result += num % 10;
            num /= 10;

            if (num == 0 && result > 9) {
                num = result;
                result = 0;
            }
        }

        return result;
    }


    public int[] shortestToChar(String S, char C) {
        int[] result = new int[S.length()];
        char[] chars = S.toCharArray();
        Arrays.fill(result, Integer.MAX_VALUE);

        int pre = -1;

        for (int i = chars.length - 1; i >= 0; i--) {
            if (chars[i] == C) {
                pre = i;
                result[i] = 0;
            } else if (pre != -1) {
                result[i] = pre - i;
            }
        }

        pre = -1;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == C) {
                pre = i;
            } else if (pre != -1) {
                result[i] = Math.min(result[i], i - pre);
            }
        }

        return result;
    }

    public int distributeCandies(int[] candies) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < candies.length; i++) {
            set.add(candies[i]);
            if (set.size() == candies.length / 2) {
                return set.size();
            }
        }

        return set.size();
    }

    public List<List<Integer>> generate(int numRows) {
        ArrayList<List<Integer>> list = new ArrayList<>();

        if (numRows == 0) {
            return list;
        }

        list.add(Collections.singletonList(1));
        if (numRows == 1) {
            return list;
        }

        list.add(Arrays.asList(1, 1));
        if (numRows == 2) {
            return list;
        }


        for (int i = 2; i < numRows; i++) {
            ArrayList<Integer> arr = new ArrayList<>(i + 1);
            arr.add(1);
            List<Integer> pre = list.get(i - 1);
            for (int j = 1; j < i; j++) {

                arr.add(pre.get(j) + pre.get(j - 1));
            }

            arr.add(1);

            list.add(arr);
        }

        return list;
    }


    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] bucket = new int[1001];


        //存入所有数
        for (int i = 0; i < arr1.length; i++) {
            bucket[arr1[i]]++;
        }


        //按arr2的顺序排序
        int index = 0;
        for (int i = 0; i < arr2.length; i++) {
            while (bucket[arr2[i]] > 0) {
                arr1[index++] = arr2[i];
                bucket[arr2[i]]--;
            }
        }


        //取出剩余的数
        for (int i = 0; i < bucket.length; i++) {
            while (bucket[i] > 0) {
                arr1[index++] = i;
                bucket[i]--;
            }
        }

        return arr1;

    }


    public int fib(int N) {

        if (N < 2) {
            return N;
        }


        int a = 0;
        int b = 1;

        for (int i = 2; i <= N; i++) {
            int temp = b;
            b = a + b;
            a = temp;
        }

        return b;
    }

    public boolean isToeplitzMatrix(int[][] matrix) {
        int width = matrix[0].length;
        int height = matrix.length;

        int i = 0;
        for (int j = width - 1; j >= 0; j--) {
            if (i >= height) {
                break;
            }


            int num = matrix[i][j];

            int y = i, x = j;

            while (y < height && x < width) {
                if (num != matrix[y][x]) {
                    return false;
                }
                y++;
                x++;
            }


            if (j == 0) {
                j++;
                i++;
            }
        }


        return true;

    }

    public List<List<Integer>> levelOrderBottom(TreeNode root) {

        ArrayList<List<Integer>> list = new ArrayList<>();

        afterOrder(root, list, 0);

        Collections.reverse(list);
        return list;
    }

    public void afterOrder(TreeNode root, ArrayList<List<Integer>> list, int step) {

        if (root == null) {
            return;
        }


        if (list.size() == step) {
            list.add(new ArrayList<>());
        }

        afterOrder(root.left, list, step + 1);
        afterOrder(root.right, list, step + 1);
        list.get(step).add(root.val);
    }

    public int countLargestGroup(int n) {
        int[] bucket = new int[37];
        int max = 0;
        for (int i = 1; i <= n; i++) {
            int sum = 0;
            int num = i;
            while (num != 0) {
                sum += num % 10;
                num /= 10;
            }
            max = Math.max(max, ++bucket[sum]);
        }


        int count = 0;
        for (int i = 0; i < bucket.length; i++) {
            if (bucket[i] == max) {
                count++;
            }
        }


        return count;
    }

    public int[] numberOfLines(int[] widths, String S) {
        char[] chars = S.toCharArray();

        if (S.length() == 0) {
            return new int[]{0, 0};
        }

        int sum = 0;


        int line = 1;

        for (int i = 0; i < chars.length; i++) {
            if (sum + widths[chars[i] - 'a'] <= 100) {
                sum += widths[chars[i] - 'a'];
            } else {
                sum = chars[i - 'a'];
                line++;
            }
        }
        return new int[]{line, sum};
    }


    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        if (nums1.length == 0) {
            return new int[]{};
        }

        //桶存储位置
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums2.length; i++) {
            max = Math.max(max, nums2[i]);
        }

        int[] bucket = new int[max + 1];
        Arrays.fill(bucket, -1);

        for (int i = 0; i < nums2.length; i++) {
            bucket[nums2[i]] = i;
        }

        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            int res = -1;

            //通过桶找到起始坐标
            int index = bucket[nums1[i]];

            for (int j = index + 1; j < nums2.length; j++) {
                //向右遍历查找
                if (nums2[j] > nums1[i]) {
                    res = nums2[j];
                    break;
                }
            }
            result[i] = res;
        }

        return result;
    }

    public List<String> binaryTreePaths(TreeNode root) {
        ArrayList<String> list = new ArrayList<>();

        binaryTreePaths(list, root, new int[]{});

        return list;
    }

    public void binaryTreePaths(List<String> list, TreeNode root, int[] arr) {
        if (root == null) {
            return;
        }


        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = root.val;

        binaryTreePaths(list, root.left, arr);
        binaryTreePaths(list, root.right, arr);


        if (root.left == null && root.right == null) {
            StringBuilder builder = new StringBuilder();
            builder.append(arr[0]);
            for (int i = 1; i < arr.length; i++) {
                builder.append("->");
                builder.append(arr[i]);
            }
            list.add(builder.toString());
        }
    }


    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val == p.val) {
            return p;
        }

        if (root.val == q.val) {
            return q;
        }


        if (p.val > root.val && q.val > root.val) {
            return lowestCommonAncestor(root.right, p, q);
        } else if (p.val < root.val && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        } else {
            return root;
        }
    }

    public List<String> fizzBuzz(int n) {

        ArrayList<String> list = new ArrayList<>(n);

        for (int i = 1; i <= n; i++) {
            if (n % 3 == 0 && n % 5 == 0) {
                list.add("FizzBuzz");
            } else if (n % 3 == 0) {
                list.add("Fizz");
            } else if (n % 5 == 0) {
                list.add("Buzz");
            } else {
                list.add(n + "");
            }
        }

        return list;
    }


    public int[] kWeakestRows(int[][] mat, int k) {
        int[] result = new int[k];


        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < mat.length; i++) {
            int count = 0;
            for (int j = 0; j < mat[i].length; j++) {
                if (mat[i][j] == 0) {
                    break;
                }
                count++;
            }
            list.add(count * 100 + i);
        }

        Collections.sort(list);

        for (int i = 0; i < result.length; i++) {
            result[i] = list.get(i) % 100;
        }
        return result;
    }

    public int[] sumZero(int n) {
        int[] arr = new int[n];

        int sum = 0;

        for (int i = 1; i < n; i++) {
            arr[i] = i;
            sum += i;
        }


        arr[arr.length - 1] = -sum;


        return arr;
    }

    public String freqAlphabets(String s) {
        char[] chars = s.toCharArray();
        StringBuilder str = new StringBuilder();

        for (int i = chars.length - 1; i >= 0; i--) {
            if (chars[i] == '#') {
                str.insert(0, (char) ((chars[i - 2] - 48) * 10 + (chars[i - 1] - 48) + 96));
                i -= 2;
            } else {
                str.insert(0, (char) (chars[i] + 48));
            }
        }

        return str.toString();
    }


    public List<Integer> postorder(Node root) {

        ArrayList<Integer> list = new ArrayList<>();

        postOrder(root, list);
        return list;
    }

    public void postOrder(Node root, ArrayList<Integer> list) {

        if (root == null) {
            return;
        }


        for (Node child : root.children) {
            postOrder(child, list);
        }


        list.add(root.val);
    }


    public TreeNode searchBST(TreeNode root, int val) {

        if (root == null) {
            return null;
        }

        if (root.val > val) {
            return searchBST(root.left, val);
        } else if (root.val < val) {
            return searchBST(root.right, val);
        } else {
            return root;
        }

    }

    public String sortString(String s) {
        int[] arr = new int[26];
        for (char c : s.toCharArray()) {
            arr[c - 'a']++;
        }


        StringBuilder str = new StringBuilder();
        int count = 0;
        while (true) {
            for (int i = 0; i < arr.length; i++) {
                if (arr[i]-- > 0) {
                    str.append((char) (i + 'a'));
                    if (++count == s.length()) {
                        return str.toString();

                    }
                }
            }

            for (int i = arr.length - 1; i >= 0; i--) {
                if (arr[i]-- > 0) {
                    str.append((char) (i + 'a'));
                    if (++count == s.length()) {
                        return str.toString();
                    }
                }
            }
        }
    }


    public List<Integer> selfDividingNumbers(int left, int right) {

        ArrayList<Integer> list = new ArrayList<>();
        for (int i = left; i <= right; i++) {
            if (selfDividingNumbers(i)) {
                list.add(i);
            }
        }

        return list;
    }

    public boolean selfDividingNumbers(int n) {
        int m = n;
        while (n != 0) {
            int i = n % 10;
            if (i == 0 || m % i != 0) {
                return false;
            }
            n /= 10;
        }
        return true;
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        // 左右等分建立左右子树，中间节点作为子树根节点，递归该过程
        return nums == null ? null : buildTree(nums, 0, nums.length - 1);
    }

    private TreeNode buildTree(int[] nums, int l, int r) {
        if (l > r) {
            return null;
        }
        int m = l + (r - l) / 2;
        TreeNode root = new TreeNode(nums[m]);
        root.left = buildTree(nums, l, m - 1);
        root.right = buildTree(nums, m + 1, r);
        return root;
    }


    public List<Integer> preorder(Node root) {
        if (root == null) {
            return new LinkedList<>();
        }
        Stack<Node> stack = new Stack<>();
        List<Integer> res = new LinkedList<>();


        stack.push(root);
        while (!stack.isEmpty()) {
            root = stack.pop();

            for (int i = root.children.size() - 1; i >= 0; i--) {
                stack.push(root.children.get(i));
            }

            res.add(root.val);
        }

        return res;
    }

    public void preorder(Node root, ArrayList<Integer> list) {
        if (root == null) {
            return;
        }

        list.add(root.val);

        for (Node child : root.children) {
            preorder(child, list);
        }

    }

    public int numSpecialEquivGroups(String[] A) {
        HashSet<String> set = new HashSet<>();
        for (String s : A) {
            //奇数
            char[] c2 = new char[s.length() / 2];
            //偶数
            char[] c1 = new char[s.length() - c2.length];

            char[] chars = s.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                if (i % 2 == 0) {
                    c1[i / 2] = chars[i];
                } else {
                    c2[i / 2] = chars[i];
                }


            }
            Arrays.sort(c1);
            Arrays.sort(c2);
            set.add(new String(c1) + new String(c2));
        }


        return set.size();
    }

    public int minDeletionSize(String[] arr) {
        if (arr[0].length() == 1) {
            return 0;
        }

        int count = 0;
        a:
        for (int i = 0; i < arr[0].length(); i++) {
            char pre = 'a' - 1;
            for (int j = 0; j < arr.length; j++) {
                if (arr[j].charAt(i) < pre) {
                    count++;
                    continue a;
                }
                pre = arr[j].charAt(i);
            }
        }

        return count;

    }


    public String[] findWords(String[] words) {
        String line1 = "qwertyuiopQWERTYUIOP";
        String line2 = "asdfghjklASDFGHJKL";
        String line3 = "zxcvbnmZXCVBNM";


        ArrayList<String> list = new ArrayList<>();

        a:
        for (String word : words) {
            int line = -1;
            for (char c : word.toCharArray()) {
                int tmp = -1;
                if (line1.indexOf(c) != -1) {
                    tmp = 1;
                } else if (line2.indexOf(c) != -1) {
                    tmp = 2;
                } else if (line3.indexOf(c) != -1) {
                    tmp = 3;
                }

                if (line != -1 && tmp != line) {
                    continue a;
                }

                line = tmp;
            }

            list.add(word);
        }


        return list.toArray(new String[]{});
    }


    public boolean canWinNim(int n) {
        return n % (4) != 0;
    }


    public List<Integer> minSubsequence(int[] nums) {
        Arrays.sort(nums);
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        int index = nums.length - 1;

        ArrayList<Integer> list = new ArrayList<>();
        int right = 0;
        while (right <= sum) {
            right += nums[index];
            list.add(nums[index]);

            index--;
        }


        return list;

    }


    public ListNode middleNode(ListNode head) {

        ListNode fast = head.next;
        ListNode slow = head;


        while (fast != null) {
            slow = slow.next;
            fast = fast.next;


            if (fast != null) {
                fast = fast.next;
            }

        }


        return slow;


    }

    public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
        ArrayList<List<Integer>> list = new ArrayList<>();

        int x = 1, y = z;

        while (x <= z && y > 0) {
            if (customfunction.f(x, y) == z) {
                list.add(Arrays.asList(x, y));
                x++;
                y--;
            } else if (customfunction.f(x, y) > z) {
                y--;
            } else {
                x++;
            }
        }

        return list;

    }

    class CustomFunction {
        // Returns f(x, y) for any given positive integers x and y.
        // Note that f(x, y) is increasing with respect to both x and y.
        // i.e. f(x, y) < f(x + 1, y), f(x, y) < f(x, y + 1)
        public int f(int x, int y) {

            return 0;
        }
    }

    public String reverseWords(String s) {
        String[] split = s.split(" ");

        for (int i = 0; i < split.length; i++) {
            char[] chars = split[i].toCharArray();

            int l = 0, r = chars.length - 1;
            char tmp;
            while (l < r) {
                tmp = chars[l];
                chars[l] = chars[r];
                chars[r] = tmp;

                l++;
                r--;
            }

            split[i] = new String(chars);
        }


        return String.join(" ", split);

    }


    public int hammingWeight(int n) {
        int count = 0;

        while (n != 0) {

            if (n % 2 == 1) {
                count++;
            }
            n /= 2;
        }

        return count;
    }

    public int[] sortArrayByParity(int[] A) {
        int[] result = new int[A.length];


        int j = 0;
        for (int i = 0; i < A.length; i++) {
            if (A[i] % 2 == 0) {
                result[j++] = A[i];
                A[i] = -1;
            }
        }

        for (int i : A) {
            if (i != -1) {
                result[j++] = i;
            }
        }

        return result;


    }

    public int findLUSlength(String a, String b) {

        if (a.equals(b)) {
            return -1;
        }

        return Math.max(a.length(), b.length());
    }


    public int smallestRangeI(int[] A, int K) {
        int min = A[0];
        int max = A[0];

        for (int i : A) {
            min = Math.min(min, i);
            max = Math.max(max, i);
        }


        if (max - min < K * 2) {
            return 0;
        } else {
            return max - min - K * 2;
        }


    }


    public int minCostToMoveChips(int[] position) {

        int even = 0;
        int odd = 0;
        for (int i : position) {
            if (even % 2 == 0) {
                even++;
            } else {
                odd++;
            }
        }


        return Math.min(even, odd);
    }


    public int countCharacters(String[] words, String chars) {

        int length = 0;
        int[] hash = new int[26];

        for (char c : chars.toCharArray()) {
            hash[c - 'a']++;
        }
        int[] map = new int[26];
        a:
        for (String word : words) {
            Arrays.fill(map, 0);

            for (char c : word.toCharArray()) {
                map[c - 'a']++;

                if (map[c - 'a'] > hash[c - 'a']) {
                    continue a;
                }

            }
            length += word.length();

        }

        return length;

    }


    public List<String> commonChars(String[] A) {

        ArrayList<String> list = new ArrayList<>();


        int[] res = new int[26];

        for (char c : A[0].toCharArray()) {
            res[c - 'a']++;
        }


        for (int i = 1; i < A.length; i++) {
            int[] temp = new int[26];
            for (char c : A[i].toCharArray()) {
                temp[c - 'a']++;
            }

            for (int j = 0; j < res.length; j++) {
                res[j] = Math.min(res[j], temp[j]);

            }
        }


        for (int i = 0; i < res.length; i++) {
            if (res[i] > 0) {

                for (int j = 0; j < res[i]; j++) {
                    list.add(String.valueOf((char) (i + 'a')));
                }
            }
        }

        return list;


    }


    public String defangIPaddr(String address) {
        return address.replace("\\.", "[.]");
    }


    public int minCount(int[] coins) {

        int count = 0;
        for (int coin : coins) {
            count += coin % 2 == 0 ? coin / 2 : coin / 2 + 1;
        }

        return count;
    }

    public int subtractProductAndSum(int n) {
        if (n == 0) {
            return 0;
        }

        int sum = 0;
        int pro = 1;


        while (n != 0) {

            sum += n % 10;
            pro *= n % 10;

            n /= 10;

        }


        return pro - sum;

    }

    ListNode head;

    public void deleteNode(ListNode node) {
        if (head.next.val == node.val) {
            head = head.next;
            return;
        }

        ListNode temp = head;

        while (temp.next != null) {
            if (temp.next.val ==node.val){
                temp.next = temp.next.next;
                break;
            }

            temp=temp.next;
        }

    }

}

